<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    //  二叉搜索树
    let Node = function (value) {
        this.value = value;
        this.right = null;
        this.left = null;
        this.isFirst = false;
    };

    class BST {
        constructor(value) {
            let node = new Node(value);
            this.root = node;
            this.count = 0;
        }

        size() {
            return this.count
        }

        isEmpty() {
            return this.count === 0
        }

        insert(value) {
            if (this.root === null) {
                this.root = new Node(value);
                this.count = 1;
            } else {
                this.root = this._insert(this.root, value);
                this.count++
            }
        }

        _insert(node, value) {
            if (node === null) {
                return new Node(value)
            }
            if (node.value === value) {
                return;
            } else if (value < node.value) {
                node.left = this._insert(node.left, value)
            } else {
                node.right = this._insert(node.right, value)
            }
            return node;
        }

        contain(value) {
            return this._contain(this.root, value)
        }

        _contain(node, value) {
            if (node === null) return false
            if (node.value === value) {
                return true
            } else if (node.left && node.value > value) {
                return this._contain(node.left, value)
            } else if (node.right && node.value < value) {
                return this._contain(node.right, value)
            }
        }

        search(value) {
            return this._search(this.root, value)
        }

        _search(node, value) {
            if (node === null) return null

            if (node.value === value) {
                return node.value
            } else if (node.left && node.value > value) {
                return this._search(node.left, value)
            } else if (node.right && node.value < value) {
                return this._search(node.right, value)
            }
            return null
        }

        preOrder(node) {
            if (node !== null) {
                console.log(node.value)
                this.preOrder(node.left)
                this.preOrder(node.right)
            }
        }

        preOrderNR(node) {
            if (!node) return;
            let stack = [],
                root;
            stack.push(node);
            while (stack.length) {
                root = stack.pop();
                if (root.right) stack.push(root.right);
                if (root.left) stack.push(root.left);
                console.log(root.value)
            }
        }

        preOrderMorris(node) {
            if (!node) return null;

            let pre;
            while (node) {
                if (!node.left) {
                    console.log(node.value);
                    node = node.right;
                } else {
                    pre = node.left;
                    while (pre.right && pre.right !== node) {
                        pre = pre.right;
                    }
                    if (!pre.right) {
                        console.log(node.value);
                        pre.right = node;
                        node = node.left
                    } else {
                        node = node.right;
                        pre.right = null;
                    }
                }
            }
        }

        inOrder(node) {
            if (node !== null) {
                this.inOrder(node.left);
                console.log(node.value);
                this.inOrder(node.right)
            }
        }

        inOrderNR(node) {
            if (!node) return
            let stack = [],
                root;
            while (true) {
                while (node) {
                    stack.push(node);
                    node = node.left
                }

                if (!stack.length) break;
                root = stack.pop();
                console.log(root.value);
                root = root.right;
            }
        }

        inOrderMorris(node) {
            if (!node) return null;

            let pre;
            while (node) {
                if (!node.left) {
                    console.log(node.value)
                    node = node.right
                } else {
                    pre = node.left
                    while (pre.right && pre.right !== node) {
                        pre = pre.right
                    }
                    if (!pre.right) {
                        pre.right = node
                        node = node.left
                    } else {
                        console.log(node.value)
                        node = node.right
                    }
                }

            }
        }

        postOrder(node) {
            if (node !== null) {
                this.postOrder(node.left)
                this.postOrder(node.right)
                console.log(node.value)
            }
        }

        postOrderNR(node) {
            if (!node) return;
            let stack = [],
                currNode = node,
                rightNode = null;
            stack.push(currNode)
            while (stack.length) {
                while (currNode.left) {
                    stack.push(currNode.left)
                    currNode = currNode.left;
                }
                currNode = stack.pop()
                while (!currNode.right || currNode.right === rightNode) {
                    console.log(currNode.value)
                    rightNode = currNode
                    currNode = stack.pop()
                }
                stack.push(currNode)
                currNode = currNode.right

            }
        }

        reverse(p1, p2) {
            if (p1 === p2) return;

            let x = p1,
                y = p1.right,
                temp;
            while (true) {
                temp = y.right;
                y.right = x;
                x = y;
                y = temp;
                if (x === p2) break;
            }
        }

        printReverse(p1, p2) {
            this.reverse(p1, p2);

            let pNode = p2;
            while (true) {
                console.log(pNode.value);
                if (pNode === p1) break;
                pNode = pNode.right;
            }

            this.reverse(p2, p1);
        }

        postOrderMorris(node) {
            if (!node) return;
            let root = new Node(null),
                pre;
            root.left = node;
            while (root) {
                if (!root.left) {
                    root = root.right;
                } else {
                    pre = root.left;
                    while (pre.right && pre.right !== root) {
                        pre = pre.right;
                    }
                    if (!pre.right) {
                        pre.right = root;
                        root = root.left;
                    } else {
                        this.printReverse(root.left, pre);
                        pre.right = null;
                        root = root.right
                    }
                }
            }
        }

        miniNum(node) {
            if (!this.root) return;
            while (node) {
                if (!node.left) {
                    return node
                }
                node = node.left
            }
        }

        removeMin(node) {
            let pNode = node,
                minNode = node.left,
                rightNode = null;
            while (minNode && minNode.left) {
                pNode = pNode.left
                minNode = minNode.left
            }
            if (minNode.right) {
                rightNode = minNode.right
            }
            pNode.left = rightNode
            return node;
        }

        maxNum(node) {
            if (!this.root) return;
            while (node) {
                if (!node.right) {
                    return node;
                }
                node = node.right
            }
        }

        removeMax(node) {
            let pNode = node,
                maxNode = node.right,
                leftNode = null;
            while (maxNode && maxNode.right) {
                pNode = pNode.right
                maxNode = maxNode.right
            }
            if (maxNode.left) {
                leftNode = maxNode.left
            }
            pNode.right = leftNode
            return node;
        }

        remove(node, e) {
            this.root = this._remove(node, e);
            this.count--;
        }

        _remove(node, e) {
            if (!node) return null;

            if (node.value > e.value) {
                node.left = this._remove(node.left, e);
            } else if (node.value < e.value) {
                node.right = this._remove(node.right, e);
            } else {
                if (node.left === null) {
                    let rightNode = node.right;
                    node.right = null;
                    return rightNode;
                } else if (node.right === null) {
                    let leftNode = node.left;
                    node.left = null;
                    return leftNode;
                }
                let successor = this.miniNum(node.right);
                successor.right = this.removeMin(node.right);
                successor.left = node.left;
                node.left = node.right = null;
                return successor;
            }
        }


        levelOrder() {
            let queue = [];
            queue.push(this.root);
            while (queue.length) {
                let node = queue.shift();
                console.log(node.value);
                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
            }
        }
    }


</script>
</body>
</html>